﻿using System.Collections.Generic;
using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 有效的括号
    {
        /// <summary>
        /// https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnbcaj/
        /// </summary>
        /// <summary>
        /// 2021-7-15
        /// 执行用时：68  ms, 在所有 C# 提交中击败了98.41%的用户
        /// 内存消耗：22  MB, 在所有 C# 提交中击败了73.64%的用户
        /// </summary>
        /// <param name="numRows"></param>
        /// <returns></returns>
        public class Solution
        {
            /// <summary>
            /// 因为只有括号，当为左括号时，stack存储右存储，如果遇到右括号，判断当前stack是否为空，或取出当前stack中的值是否与右括号不相等，则返回false。
            /// 最后判断当前stack 长度为0，才是有效括号
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public bool IsValid(string s)
            {
                Stack<char> stack = new Stack<char>();
                foreach (var c in s)
                {
                    switch (c)
                    {
                        case '(':
                            stack.Push(')');
                            break;
                        case '[':
                            stack.Push(']');
                            break;
                        case '{':
                            stack.Push('}');
                            break;
                        case ')':
                        case ']':
                        case '}':
                            if (stack.Count == 0 || stack.Pop() != c) return false;
                            break;
                    }
                }
                return stack.Count == 0;
            }
        }

        ITestOutputHelper output;

        public 有效的括号(ITestOutputHelper output)
        {
            this.output = output;
        }


        [Fact]
        public void Test1()
        {

            Solution solution = new Solution();
            var vv = solution.IsValid("()");
            Assert.True(vv);

            vv = solution.IsValid("(]");
            Assert.False(vv);

            vv = solution.IsValid("()[]{}");
            Assert.True(vv);

            vv = solution.IsValid("([)]");
            Assert.False(vv);

            vv = solution.IsValid("{[]}");
            Assert.True(vv);


        }
    }
}
